package com.xyhuo.leetcode.november;

/**
 * 网格中的最小路径代价
 * https://leetcode.cn/problems/minimum-path-cost-in-a-grid/
 *
 * @time 2023/11/22
 */
public class MinPathCost {

//    public static void main(String[] args) {
////        int[][] grid = {{28, 35, 29, 5, 13, 17, 18, 23, 14}, {30, 15, 12, 27, 2, 26, 25, 19, 7}, {1, 16, 34, 21, 9, 3, 20, 24, 8}, {4, 33, 22, 11, 31, 0, 6, 10, 32}};
////        int[][] moveCost = {{87, 46, 11, 33, 55, 26, 26, 56, 23}, {77, 56, 72, 49, 35, 18, 37, 66, 37}, {54, 40, 62, 1, 64, 49, 95, 81, 77}, {80, 7, 76, 71, 91, 67, 75, 84, 52}, {65, 11, 13, 15, 9, 34, 10, 98, 20}, {1, 95, 100, 61, 33, 47, 28, 100, 44}, {39, 56, 94, 7, 64, 91, 66, 34, 70}, {37, 99, 62, 7, 23, 78, 74, 89, 97}, {84, 41, 63, 42, 84, 15, 46, 31, 11}, {60, 36, 27, 25, 37, 18, 4, 90, 43}, {35, 83, 90, 37, 91, 27, 61, 99, 53}, {85, 2, 98, 99, 67, 70, 38, 91, 68}, {66, 46, 7, 99, 26, 81, 95, 51, 51}, {41, 96, 66, 84, 61, 73, 78, 28, 63}, {38, 34, 49, 55, 35, 29, 93, 5, 28}, {3, 30, 80, 20, 23, 10, 93, 40, 33}, {8, 86, 47, 15, 45, 84, 47, 19, 58}, {72, 5, 76, 82, 60, 50, 13, 74, 38}, {4, 8, 25, 38, 29, 4, 60, 81, 21}, {65, 50, 74, 32, 9, 47, 71, 55, 14}, {90, 30, 92, 51, 45, 51, 4, 85, 22}, {30, 56, 1, 45, 63, 72, 91, 73, 60}, {51, 61, 53, 49, 44, 99, 11, 5, 3}, {24, 54, 91, 11, 5, 30, 50, 89, 44}, {87, 97, 46, 92, 93, 41, 64, 73, 15}, {94, 76, 90, 80, 30, 9, 88, 8, 33}, {50, 34, 4, 63, 49, 90, 46, 55, 16}, {10, 46, 80, 21, 97, 69, 70, 85, 31}, {10, 66, 74, 43, 65, 45, 85, 34, 91}, {82, 26, 77, 10, 2, 5, 89, 39, 4}, {80, 70, 89, 73, 54, 61, 100, 89, 23}, {30, 66, 80, 51, 3, 34, 92, 100, 63}, {74, 15, 4, 33, 37, 3, 87, 76, 92}, {44, 43, 77, 99, 27, 1, 23, 10, 8}, {8, 74, 17, 35, 31, 84, 97, 98, 34}, {99, 9, 28, 43, 55, 39, 93, 64, 93}};
//
//        int[][] grid = {{4, 5, 13, 21}, {10, 22, 1, 25}, {18, 26, 28, 29}, {8, 16, 6, 20}, {14, 0, 12, 27}, {11, 30, 9, 19}, {23, 7, 3, 17}, {31, 2, 15, 24}};
//        int[][] moveCost = {{94, 73, 25, 55}, {73, 59, 68, 75}, {85, 16, 44, 82}, {27, 46, 51, 52}, {56, 53, 36, 100}, {25, 77, 95, 55}, {77, 12, 45, 10}, {77, 5, 90, 74}, {50, 12, 87, 7}, {53, 27, 29, 49}, {27, 14, 39, 12}, {69, 42, 36, 96}, {36, 51, 33, 91}, {10, 92, 83, 82}, {63, 36, 61, 73}, {92, 47, 73, 48}, {49, 15, 34, 34}, {53, 67, 17, 51}, {15, 3, 81, 26}, {22, 37, 98, 93}, {61, 3, 100, 25}, {34, 21, 90, 81}, {21, 58, 6, 11}, {1, 77, 25, 57}, {69, 43, 43, 39}, {16, 16, 42, 23}, {85, 47, 35, 76}, {70, 64, 2, 4}, {1, 2, 39, 14}, {41, 74, 25, 50}, {93, 38, 22, 45}, {50, 60, 90, 92}};
//        MinPathCost minPathCost = new MinPathCost();
//        int result = minPathCost.minPathCost(grid, moveCost);
//        System.out.println(result);
//    }

    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] pd = new int[m][n];
        for (int i = 0; i < n; i++) {
            pd[0][i] = grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Integer tmpCost = null;
                for (int k = 0; k < n; k++) {
                    int tmp = grid[i - 1][k];
                    int cost = moveCost[tmp][j];
                    int nowCost = pd[i - 1][k] + cost;
                    if (null == tmpCost || nowCost < tmpCost) {
                        tmpCost = nowCost;
                    }
                }
                pd[i][j] = tmpCost + grid[i][j];
            }
        }
        int result = pd[m - 1][0];
        for (int i = 1; i < n; i++) {
            if (pd[m - 1][i] < result) {
                result = pd[m - 1][i];
            }
        }
        return result;

    }
}
